package leetcode.editor.cn.q1_300.q;

/**
 * @author qidi
 * @date 2021-12-07 15:31:46
 */
class Q0050_PowxN {

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public double myPow(double x, int n) {
            if (x == 0) return 0;
            if (x == 1) return 1;
            if (x == -1) return n % 2 == 0 ? 1 : -1;
            if (n == 0) return 1;
            if (n == 1) return x;
            if (n == -1) return 1 / x;

            long nn = Math.abs((long) n);
            double[] nums = new double[32];
            int length = 0;
            double cur = 1;
            while (cur <= nn) {
                nums[length] = cur;
                cur *= 2;
                length++;
            }

            for (int i = length - 1; i >= 0; i--) {
                if (nn >= nums[i]) {
                    nn -= nums[i];
                } else {
                    nums[i] = -1.0;
                }
            }

            double res = x;

            for (int i = 0; i < length; i++) {
                if (i != 0) {
                    res *= res;
                }
                if (nums[i] != -1) {
                    nums[i] = res;
                }
            }

            res = 1;
            for (int i = 0; i < length; i++) {
                if (nums[i] != -1) res *= nums[i];
            }

            return n > 0 ? res : 1 / res;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q0050_PowxN().new Solution();
        System.out.println(solution.myPow(2.0, 10));
        System.out.println(solution.myPow(2.1, 3));
        System.out.println(solution.myPow(2.0, -2));
    }
}